#include <mergeSort.h>
#include <stdlib.h>
#include <stdio.h>

static void Merge(ElementType A[], ElementType Tmp[], int Lpos, int Rpos, int Rend){
    int i, Lend, TmpPos=Lpos;
    int num = Rend - Lpos + 1;
    Lend = Rpos - 1;

    while(Lpos <= Lend && Rpos <= Rend){
        if(A[Lpos] < A[Rpos]){
            Tmp[TmpPos++] = A[Lpos++];
        }else{
            Tmp[TmpPos++] = A[Rpos++];
        }
    }

    while(Lpos <= Lend){
        Tmp[TmpPos++] = A[Lpos++];
    }

    while(Rpos <= Rend){
        Tmp[TmpPos++] = A[Rpos++];
    }

    for(i = 0; i < num; Rend--, i++){
        A[Rend] = Tmp[Rend];
    }
}

static void MSort(ElementType A[], ElementType Tmp[], int Left, int Right){
    int Center;
    int i;
    if(Left < Right){
        Center = (Left + Right) / 2;
        MSort(A, Tmp, Left, Center);
        MSort(A, Tmp, Center + 1, Right);
        Merge(A, Tmp, Left, Center + 1, Right);
    }
}

void MergeSort(ElementType A[], int N){
    ElementType *TmpArray;

    TmpArray = malloc(N * sizeof(ElementType));
    if(TmpArray != NULL){
        MSort(A, TmpArray, 0, N - 1);
    }else{
        printf("malloc error");
    }
}